package com.algomypractice.linkedlist;

import com.sourcestruct.linearlist.SingleLinkedList;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/6/5
 * @description: 单链表的环问题 Linked List Cycle
 * Given a linked list, determine if it has a cycle in it.
 * <p>
 * Follow up: Can you solve it without using extra space?
 * <p>
 * 如何判断一个单链表中有环？
 * ------------------------------------------------------------
 * Linked List Cycle II
 * Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
 * <p>
 * Follow up: Can you solve it without using extra space?
 * <p>
 * 如何找到环的第一个节点？
 * -- 关于这个问题，有点数学方面的疑惑，在下面这个网址得到解决
 * https://blog.csdn.net/sinat_35261315/article/details/79205157
 */
public class SingleLinkedRing {

	public static void main(String[] args) {
		SingleLinkedList lastnode = new SingleLinkedList(1, null);
		SingleLinkedList nodea = new SingleLinkedList(2, lastnode);
		SingleLinkedList nodeb = new SingleLinkedList(3, nodea);
		SingleLinkedList nodec = new SingleLinkedList(4, nodeb);
		lastnode.setNext(nodec);
		SingleLinkedList noded = new SingleLinkedList(5, nodec);
		///1.判断是否存在
		//System.out.println(determineByArrray(noded));
		//System.out.println(determineByTrace(noded));

		//2.查找环的第一个节点
		System.out.println(findRingStartByArray(noded));
		System.out.println(findRingStartByTrace(noded));

	}

	//region	判断是否有环I

	/**
	 * 1.通过动态数组判断(需要新的空间)
	 * 遍历链表存入 ArrayList 直到遇到哈希值相同的元素返回 true
	 * 不能简单地认为去找最后的节点，判断其后继节点是否为空！因为如果不去存储内存地址判断，执行了上万遍，仍然没有找到最后的节点，那么这个单链表是否有环仍然判断不出来！
	 *
	 * @return
	 */
	public static boolean determineByArrray(SingleLinkedList node) {
		//边界条件判断
		if (node == null) {
			return false;
		}
		List<SingleLinkedList> list = new ArrayList<>();
		SingleLinkedList curr = node;
		while (curr != null) {
			if (list.contains(curr)) {
				return true;
			}
			list.add(curr);
			curr = curr.getNext();
		}
		return false;
	}

	/**
	 * 2.通过追及问题
	 * 如果遇到null,那么说明没有环，因为后继节点只有一个，只有非环才可能出现 null 的后继
	 *
	 * @param node
	 * @return
	 */
	public static boolean determineByTrace(SingleLinkedList node) {
		if (node == null) {
			return false;
		}

		SingleLinkedList currA = node;
		SingleLinkedList currB = node;
		while (currB.getNext() != null && currB.getNext().getNext() != null) {
			currA = getSlow(currA);
			currB = getFast(currB);
			if (currA.equals(currB)) {
				return true;
			}
		}
		return false;
	}

	//endregion

	//region	找到环的第一个节点II

	/**
	 * 用数据既浪费时间 O(n2) 又浪费空间
	 *
	 * @param node
	 * @return
	 */
	public static SingleLinkedList findRingStartByArray(SingleLinkedList node) {
		if (node == null) {
			return null;
		}
		List<SingleLinkedList> list = new ArrayList<>();
		SingleLinkedList curr = node;
		while (curr != null) {
			for (int i = 0; i < list.size(); i++) {
				if (list.get(i).equals(curr)) {
					return list.get(i);
				}
			}
			list.add(curr);
			curr = curr.getNext();
		}
		return null;
	}

	/**
	 * @return
	 */
	public static SingleLinkedList findRingStartByTrace(SingleLinkedList node) {
		if (node == null || node.getNext() == null || node.getNext().getNext() == null) {
			return null;
		}
		SingleLinkedList slow=node;
		SingleLinkedList fast=node;
		SingleLinkedList cross=null;
		while (fast.getNext()!=null||fast.getNext().getNext()!=null){
			slow=getSlow(slow);
			fast=getFast(fast);
			if (slow.equals(fast)){
				cross=slow;break;
			}
		}
		if (cross==null){
			return null;
		}
		//找到相遇点后，从起点和相遇点同时出发两个慢指针，直到相遇
		SingleLinkedList newslow=node;
		while (!cross.equals(newslow)){
			newslow=getSlow(newslow);
			cross=getSlow(cross);
		}
		return newslow;
	}

	//endregion


	private static SingleLinkedList getSlow(SingleLinkedList node) {
		return node.getNext();
	}

	/**
	 * 获取快速下的节点（需要首先判断是否为空！）
	 *
	 * @param node
	 * @return
	 */
	private static SingleLinkedList getFast(SingleLinkedList node) {
		return node.getNext().getNext();
	}


}
